/**
 * Created with IntelliJ IEDA.
 * Description:
 * User:86186
 * Date:2023-05-07
 * Time:20:21
 */

/**
 * JZ33 二叉搜索树的后序遍历序列
 */

public class VerifySquenceOfBST {
    public static void main(String[] args) {
        int[] nums = new int[]{5,7,6,9,11,10,8};
        System.out.println(VerifySquenceOfBST(nums));
    }
    /**
     * 1.二叉搜索树是指父亲节点大于左子树中的全部节点，但是小于右子树中的全部节点的树。
     * 2.该题我们约定空树不是二叉搜索树
     * 3.后序遍历是指按照 “左子树-右子树-根节点” 的顺序遍历
     * @param sequence
     * @return
     */
    public static boolean VerifySquenceOfBST(int [] sequence) {
        if (sequence == null || sequence.length == 0) {
            return false;
        }
        return Verify(sequence, 0, sequence.length - 1);
    }

    private static boolean Verify(int[] sequence, int left, int right) {
        if (right - left <= 0) {
            return true;
        }
        int num = sequence[right];
        int mid = left;
        while (mid < right && num >= sequence[mid]) {
            mid++;//找到左右子树交界之处
        }
        for (int i = mid; i <= right; i++) {
            //对比右子树中的节点的大小
            if (num > sequence[i]) {
                return false;
            }
        }
        return Verify(sequence, mid, right - 1) && Verify(sequence, left, mid - 1);
    }
}
